Computer Science Department
TECHNICAL REPORT
MICRO SPITBOL
Robert B. K. Dewar
Martin Charles Golumbic
Clinton F. Goss
October I979
Report No. Oil
K)
NEW YORK UNIVERSITY
Department of Computer Science
Courant Institute of Mathematical Sciences
251 MERCER STREET, NEW YORK, N.Y. 10012
MICRO SPITBOL
By
Robert B. K. Dewar
Martin Charles Golumbic
Clinton F. Goss
October I979
Report No. Oil
This material is based upon work supported in part by the National Science
Foundation under Grant No. MCS78-O382O.
Any opinions, findings, and conclusions or recommondations expressed in this
publication are those of the authors and do not necessarily reflect the
views of the National Science Foundation.
Abstract
A compact version of MACRO SPITBOL, a compiler/ interpreter for a
variant of SNOBOLU, has been developed for use on microcomputer systems.
The techniques for producing an implementation are largely automatic in
order to preserve the integrity and portability of the SPITBOL system.
These techniques are discussed along with a description of an initial
implementation on a 65K byte minicomputer. An interesting theoretical
problem which arises when using procedures which compact the interpretive
object code is also analyzed.
Keywords: SNOBOLii, Compiler, Interpretive code, Microprocessors,
Portability, Weighted Interval Graph
MACRO SPITBOL (1"! is a compiler/ interpreter for a variant of SNOBOLU (3),
SPITBOL (k) , which has been implemented on a variety of large computers.
MICRO SPITBOL is an adaptation of the system for use on micro and
minicomputers which compiles a language identical to MACRO SPITBOL with the
exclusion of real arithmetic. The goal was to preserve the structure and
machine independence of the system while allowing for the added constraints
imposed by small computers, particularly the severe limitations on memory and
address size. We also intended that the process for implementing MICRO
SPITBOL on a minicomputer be largely automated. In this way we preserve
the integrity of the well-tested MACRO SPITBOL source code while allowing
for easy updating to new versions.
These goals were attained by encoding the MACRO SPITBOL source code,
written in the MINIMAL assembly language (5), into a compact
microcomputer assembly language, MICRAL. In a MACRO SPITBOL implementation
the MINIMAL source code is translated into the target machine's assembly
language and directly executed; The target MICRO SPITBOL machine emulates
a standard virtual microcomputer (MICRAC) which executes MICRAL code. This
interpretive approach preserves the portability of MINIMAL programs while
dealing with the problems and constraints imposed on MICRO SPITBOL.
MICRO SPITBOL is implemented on the Incoterm SPD 20/U0 (6), a 65K
byte minicomputer, and versions are in preparation for microcomputers based
on the IMS 808O and M68OO processors. Th Incoterm implementation has been
exercised with an extensive test package and appears very sound. It
provides about 2/5 of memory for the user heap in which UOO to 500
SPITBOL statements may be compiled. The current version executes an average
of 20 SPITBOL statements per second; This is l/lUO the execution speed of
the CDC 6600 version.
MICRAL - Micro Computer Assembly Language
MICRAL (2) is an encoding of MINIMAL suitable for direct translation to
an interpretive form to run on a mini or microcomputer system with a I6 bit
addressing structure and 8 bit bytes. The layout of a MICRAL program and the
environment in which it runs are similar to that of a MINIMAL program. However,
MICRAL source code is largely non-symbolic; Most of the work in converting
MICRAL to its interpretive form involves address resolution, a feature
available on even the most primative assemblers.
Unlike MINIMAL, MICRAL assumes no minimum hardware configuration since
its machine code is interpretive. In fact, the object code for a given MICRAL
program does not vary among machines with the exception of absolute addresses.
Thus the sophistication of the target machine's instruction set determines
only the speed at which the MICRAL object code is interpreted and not the
size of the code, as in MINIMAL.
The general format of MICRAL source code is typical of many assembly
languages. The opcode is one of 80 mnemonic instructions which is translated
into a single byte (x'OO' to x'UF'). The operand field is a (possibly empty)
series of items separated by commas. Each item is one of the following:
1) A two or four digit hexidecimal number which is assembled into one
or two object bytes j
2) A five character label appearing in the MICRAL program or a system
subroutine. This is eventually translated into the two byte absolute
address of the label;
3) A five character label preceded by a '+' or '-'. This form of an
address reference is used to generate a special single byte address
which will be discussed later.
To represent MINIMAL operands in MICRAL, the byte following the opcode
is used to specify the format of the first two operands. This byte, the
operand header byte, contains information about the first operand in its
four low order bits and information about the second operand in its four
high order bits. In frequent cases (references to the contents of the six
virtual registers) , the MINIMAL operand is completely specified in the header
byte.
For example, the MINIMAL instruction < MOV WA,-(XS) > is encoded in
MICRAL as < MOV 90 > since x'O' is the four bit code for the contents of
the WA register and x'9' indicates the contents of the word indexed by (XS)
with a pre-decrement on XS. If additional fields are required to fully
specify a MINIMAL operand, they directly follow the operand header byte.
The fields for the first two operands may be followed by a field for the
possible third operand. For example, the MINIMAL < BEQ WA,=X'00FF' , LABEL >
would be encoded as < BEQ BO, OOFF, LABEL > since x'B' indicates a literal
value for the second MINIMAL operand.
In accordance with the space efficient philosophy of MICRAL there are
several modifications we apply to the language as we have described it.
First we restrict all literal values and offsets to be in the range
to x'7FFF' . This allows literals in the range to x'7F' to be expressed as
a single byte whose value is x'80'+literal.
In a similar style, we convert local memory references to a single byte
by requiring that all labels in the MICRAL program and system routines take
on a value less than x'8000'. We express a jump address, ADR, which is in
the range (L - x'l+O') to (L + x'3F') (where L is the current location) as a
single byte containing (L + x'CO' - ADR). These short branch instructions are
recognized during the translation from MINIMAL to MICRAL and are indicated
by substituting '-LABEL' or '+LABEL' for 'LABEL' whenever LABEL is in
range.
The final and most space efficient optimization employed is the use of
macros. MICRAL macros utilize the I76 unused opcodes x'50' to x'FF' for
representing sequences of bytes in the MICRAL object code. These sequences of
bytes may be a single MICRAL instruction, part of an instruction, or several
instructions. Note that macros never include bytes corresponding to the one
byte offset form of jump addresses, so the question of where to count the
offset from does not arise. Also, a macro opcode may never be substituted for
a sequence of bytes which have an embedded label in the source code. This
eliminates jumping into the 'middle' of a macro. Also, it is not possible to
embed a macro in another macro, thus eliminating the necessity for
environment stacking when interpreting the macros.
Macros may be interpreted by the MICRAC emulator in one of two ways.
A table of the MICRAL bytes corresponding to each macro may be referenced when
a macro is encountered. The emulator interprets the bytes obtained from the
macro table as if they had appeared in the MICRAL program. The number of
bytes for each macro is also maintained within the macro table and, when the
macro bytes are exausted, interpretation returns to the main byte string.
Alternately, some or all of the macros may be directly hand encoded into
the target machine language. This latter approach requires more space, but
increases execution speed.
The PD/FMS Implementation
The Incoterm SPD 20/i+0 is a byte oriented single address minicomputer
with indexing and multi-level indirect addressing. It supports up to 65K
bytes of magnetic core memory with a cycle time of 1.6 microseconds. MICRO
SPITBOL is implemented under the Program Development/File Management System
(PD/FMS) (7) which provides for task control and device handling via a package
of relocatable routines.
Minimum hardware for running MICRO SPITBOL consists of the central
processor with 65K bytes of memory, a CRT/keyboard unit, and a 10 megabyte
cartridge disk drive. Additional supported hardware includes 7 CRT/keyboard
units, a printer, and 3 cartridge disk drives.
The details of the PD/EMS implementation were as follows:
The MACRO SPITBOL source code, written in MINIMAL, was translated to
MICRAL source code by MICTRAN, a program coded in SPITBOL. It is a variation
of a SPITBOL translator used for generating native assembly code from
MINIMAL. It recognizes the short form of literals and branch instructions
as described earlier. The program was run on a CDC 6600 and processed the
10,000 MINIMAL instructions in 20 cpu seconds. Figure 1 is an example of the
code produced by MICTRAN. The MICRAL source code along with the error text
file were then exported to the Incoterm system where the remainder of the
implementation was done.
The next stage was to determine the sequences of macros to employ in
translating the MICRAL source code to SPD assembly code (8). We first examined
the problem theoretically to determine whether there is an algorithm for giving
optimal or near optimal results. The problem is interesting since, although the
computation may be performed in polyiiomial time, the complexity of the optimal
algorithm is a polynomial whose degree depends on the number of macros chosen:
finding the u macros which minimize the length of t\ bytes of object code is
OCC'H't) /(d-2).') where -t is the maximum length of a macro. Another approach
which produces near optimal results and does allow embedding of macros requires
0(i:)(T)+-^'£logpT]) ) time. The analysis of this problem is presented in the
appendix.
In practice, this theoretical complexity is troublesome since version
3.3B of MICRO SPITBOL requires 23,110 bytes of MICRAL object code before
macro substitution. Also, implementation of the algorithms analyzed in the
appendix is difficult due to the numerous constraints on the allowable
macros. Since macros may not contain short branches or embedded labels,
choosing macros must be done from the source code and not the resulting byte
string. Also, since additional short branches become available as macros are
introduced, the computation of the length of the object code after a macro
substitution is dependent on many factors.
Due to the desire for a speedy implementation, it was decided to restrict
macros to a single instruction or part of an instruction and no use of hand
encodings or short branches was made. The MICRAL source code was sorted
lexicographically with the opcode field as the first key and the operand
field as the second key. The sorted list was then scanned by hand to count the
number of each operational MICRAL instruction or part instruction. The number
of bytes saved by converting each sequence to a macro was then computed for
each such instruction and multiplied by the number of occurrences. The I76
byte sequences which produced the highest savings were chosen as macros.
The MICRAL source code and the chosen macros were then processed by
MICASM, which translates MICRAL to SPD assembly source code (see Figures 2
and 3). This program is coded in SPD assembly language and processes 65 lines
per second. The resulting assembly language file was then assembled into a
relocatable module. The size of that module with macro substitutions is
17,920 bytes, an improvement of 5,190 bytes over the corresponding module
without macro substitutions.
7
To interpret the MICRAL object code, another module was included in
the absolute assembly. This module, known as the MICRAC emulator, consists of
3,020 lines of code and takes 2,230 bytes of memory. Since its size is small
compared to the MICRAL object code, the emulator is one area of the system in
which speed considerations took priority over space.
Finally, a set of modules consisting of PD/FMS routines for task control,
timer control, and screen, disk, and printer handling were included in the
absolute assembly. These routines are accessed by SPITBOL through a set of
system routines which are called directly by the MICRAL code. The system
routines were coded in SPD assembly language and are part of the mainline
MICRO SPITBOL file (the absolute assembly). In addition to the system routines,
this file contains the macro sequences and allocates space for the relocatable
modules and the SPITBOL heap. It is 51^0 lines of code and occupies the full
65K bytes, 28k bytes of which are the user heap.
The PD/FMS implementation has been exercised on a variety of test
programs and appears very stable. Performance evaluation was done with a
package of 2k programs which have an average length of 70 statements. The
test set was run under version 3.3B of MACRO SPITBOL on the CDC 66OO for
comparison. MICRO SPITBOL compiled at an average rate of I.3 statements per
second and executed at 19.7 statements per second. The corresponding values for
MACRO SPITBOL were I86.9 statements per second for compilation and 2,829
statements per second for execution.
Conclusion
The implementation of MICRO SPITBOL was broken down into two major
stages.
First, the design and implementation of programs for converting from
MINIMAL to the interpretive MICRAL code, choosing appropriate macros, and
converting from MICRAL to assembly language, required about three man-months
work.
The second stage entailed work specific to the PD/FMS implementation.
This included coding the MICRAC emulator and system routines in SPD assembly
language which, for the PD/FMS implementation, took about 1 man-month work.
For subsequent implementations it is only this latter stage which is needed
since the MICRAL object code and macros are fixed for a given version of
MICRO SPITBOL and only minor changes in MICASM are necessary to accomodate
various native assembly language formats.
Also, since the process of translation for MICRAL is now automated, any
program coded in MINIMAL may now be implemented by this scheme.
The PD/FMS version currently allows lj-00 to 500 'typical' SPITBOL
statements to be compiled. Again, since the MICRAL object code does not vary
among implementations, this figure should remain fairly constant for
microcomputers with 65K bytes of memory.
The cost of the extra level of interpretation necessary to emulate the
MICRAC machine is evident in the two order drop in execution speed from MACRO
SPITBOL on the CDC 660O to the PD/FMS implementation. However, the Incoterm
instruction set is rudimentary compared to other target microcomputers, so
an improvement in execution speed may be expected on other processors. Extra
speed may also be gained by utilizing some of the unused design features of
MICRAL such as hand encodings for macros. Also, a better selection of
9
substitution macros will have a positive effect on both processing speed and
space. Better macros may be selected by implementing one of the algorithms
suggested in the appendix, with the possible addition of some efficient
heuristics.
Due to the decreasing cost of memory, the space constraints experienced
in this implementation will probably disappear. Memory may become so inexpensive
that a direct translation of the MINIMAL code to the target machine code
would be preferable for small MINIMAL programs. However, for large MINIMAL
programs, or on processors with a low level instruction set, the techniques
used in the implementation of MICRO SPITBOL may be more suitable. Since these
systems are typically single-user, the availability of very high level
languages outweighs the loss of processing speed for many applications.
10
Appendix
We now analyze the problem of finding a set of macro substitutions which
minimizes the space required for the object code and macro table. We ignore
the complications which arise when the short form of branches are used in the
object code byte string since we have not implemented this aspect of
MICRAL.
Let B = <b]^,...,b^> be a sequence of bytes. The length of B is denoted
|b| = ri. A subsequence of B, <b^,..,,b.>, is denoted B(i:j).
A macro set is a set M = {m-|^, . . . ^m^) where each macro m^ is a sequence
of bytes. The size of the macro table corresponding to M is given by
■0
Mm|| = I ItBil .
i=l
Since macros may not include a labelled byte other than the first byte, macros
tend to be short compared to IbI. To aid in the analysis, we restrict the
length of macros, Im. I < -t .
A macro substitution is an operation on a byte sequence in which all
occurrences of a given subsequence of bytes are replaced by a single byte.
In case of overlapping occurrences of the subsequence, the leftmost occurrence
is replaced. The byte sequence resulting from the substitution of all macros in
a macro set, M, on a byte sequence, B, is denoted B(M) . The goal is to find,
for a given byte sequence, B, a macro set, M, which minimizes the length
function
l(b,m) = |b(m)| + ||m||
11
We shall analyze the worst case involved in a complete search strategy.
For .1=1, the problem reduces to finding the best single macro for a byte
sequence. Algorithm A performs this function using a table, FREQ, which maps
subsequences of B onto a count of their occurrences in B.
Algorithm A:
1) For k from 1 to ■t-'i-, perform steps 2 and 3-
2) For each subsequence of B, B(i:i+k.), increment FREQ(B( i : i+k) ) .
3) Set m(k) to a subsequence such that FREQ(m(k)) is maximal. Then set:
L(B,{m(k)}) = |b| - (|m(k) !-l)*(FREQ(m(k))-l) + 1
h) The best macro is the m(i) which minimizes L(B,{m(k)}) in step 3,
5) Substitute the macro m(i) in B.
Steps 2 and 3 are iterated over 0(-{,) times. Step 2 requires 0{t\) time
to scan the subsequences and the map FREQ, if implemented as a balanced binary
search tree, requires ©(loggT]) to maintain. Step 3 is linear if, during step
2, a pointer to the macro with the greatest FREQ is kept. Step h may also be
done in this fashion in linear time. Performing step 5 may be done by a
modification of the deterministic finite automaton pattern matching algorithm
presented in Morris and Pratt (9) and expanded in Aho, Hopcroft, and Ullman (10)
This algorithm requires 0(|b| + |m(i)|) = 0{T\+'t) time. Note that we perform
step 5 by finding the leftmost occurrence of m(i), substitute for it, and
continue to the right.
Therefore, Algorithm A runs in OCi^+'tl-Ti'D-oggTi) time.
For u > 1, one would expect that an iterative application of Algorithm A
would be effective. However, an optimal choice for the first macro does not
12
necessarily lead to an optimal macro set. For example, if
B=<j,a,b,c,d,e,f,m,r,h,a,b,c,d,e,g,k,c,d,e,f,n,s,h,a,b,c,p>
a choice of m^ = <a,b,c,d,e> yields L(B,[m^}) = 25 which is optimal for io=l.
However, any choice for ra will force L(B,(m^,m }) > 25. If ^-^ = <c,d,e,£>
and m = <h,a,b,c>, then L(B,[m^}) = 26 and UB ,[m^,m^]) = 2U.
Furthermore, our algorithm for pattern matching may not produce optimal
results in cases where a macro overlaps itself. Substituting for the second
occurrence in an overlapping pair may lead to a better choice for other
macros. This forces the recognition of each occurence of a macro and treatment
of overlapping occurences as separate cases.
We now characterize the problem of finding an optimal macro set by a
graph theoretic representation.
A weighted graph G = (V,E,W) consists of a binary relation E over a finite
set V of vertices, and an integer valued mapping W defined over V, G is an
interval graph if its vertices can be put into 1-1 correspondence with a set of
intervals on a line so that two vertices are adjacent if and only if their
corresponding intervals intersect. If B is a sequence of bytes, G(B), the
weighted interval graph corresponding to B, is defined as follows: Each vertex
in V represents a substring of B which may be used as a macro j Vertices v. and
v. are connected by an edge in E iff the occurrences of the substrings represented
by V. and v. overlap in B. If V is a vertex representing an occurrence of the
substring m, then W(v) = !m| - 1 .
If S is a subset of vertices from V, the subgraph of G induced by S,
denoted G , consists of all vertices of S together with all edges from E which
connect those vertices.
To construct G(B), the ©(rj-t) possible macros in B are scanned and one
vertex is added to V for each. Whenever a vertex is added to V, edges are
13
added to E for each overlapping macro pair. Since adding edges takes O(-c^)
time with efficient data structures for the graph, G(B) is constructed in
OCri-t ) time.
To find the macro set, M, which minimizes L(B,M), we apply the following
algorithm:
Algorithm B:
1) Calculate G(B).
2) Partition the vertices of G(B) such that each partition contains
vertices which represent occurrences of identical substrings in B.
3) Let C be the set of all possible combinations of u partitions. For
each set of combinations in C perform step h.
k) Let S be the vertices in the D partitions. Let M be the macro set
consisting of the u distinct byte sequences corresponding to the
vertices of S. Occurrences of the macros in M are chosen in B
such that no occurrences overlap. The problem of choosing the best
set of occurrences is analogous to finding the maximum weighted
independent set of vertices, I , in G . Then
L(B,Mg) = |B| - I W(v) + I W(s) .
vel seS
5) The macro set, M, which minimizes L(B,M) is then determined by
choosing an M which minimizes L(B,M ) in step h.
o o
Gilmore and Hoffman (11) characterized interval graphs by showing them
to be a subclass of chordal graphs. This class of graphs has the property
that, for every simple cycle [v, ,v , ,,.,v ,v ] (n>3), there is an edge
(v.,v.) in E such that v. and v. are in the cycle but the edge is not.
1 J 1 J ■' ^
11;
2
Gavril (12) gives an 0(|v| ) algorithm for finding the maximum weighted
independent set of a chordal graph. The algorithm is also presented in
Golumbic(13) with suitable data structures. See also Booth and Leuker (lU).
, 2
Thus, step 3 nisy be performed in 0((utv) ) time (note that the number of
vertices in any induced subgraph is bounded by i:)ri). Step 3 must be performed
at most (^ ; times. Hence, the worst case time complexity of algorithm B is
o((Tl^^ + {^y^f (^3) ,
which is, in terms of the length of the input string, a polynomial whose
degree depends on the constant u. In the example of this paper, r] is 23,000,
u is 176, and a reasonable -t would be 20. With values in this range, the
above complexity approximates and is bounded by
o((^^)'^^ / (13-2):) .
Since the time complexity of Algorithm B is high for this application,
an effective algorithm for finding a near optimal solution is needed. One
such heuristic approach would', be an iterative application of Algorithm A
whose time complexity is
0(u(Ti+^^Log2Ti)) .
Such an approach may potentially produce better results than Algorithm
B since it allows the embedding of macros within other macros, a feature
prohibited in Algorithm B. Although, one could theoretically include this
embedding feature in a method similar to Algorithm B by using the weighted
overlap graph model as described in Gavril (15) and Golumbic( I3) •
15
EXIXR EXIXR RTN
MOV 9k MOV XR,-(XS) STACK RESULT
EXITS EXITS RTH
LCW 014 LCH XR LOAD CODE WORD
MOV 37 MOV (XR),XL LOAD ENTRY ADR
BRI 03 BRI XL EXECUTE NEXT CODE
EXNAM EXNAF RTN
MOV 93 MOV XL,-(XS) STACK NAh'E BASE
MOV 90 MOV WA,-(XS) STACK NAME OFSET
BRN EXITS BRN EXITS DO NEXT CODE WORD
EXNUL EXNUL RTN
MOV 9B, NULLS MOV =NULLS,-(XS) STACK NULL VALUE
BRN EXITS BRN EXITS DO NEXT CODE WORD
FXSID EXSID RTN
MOV OA 25 MOV CURID,WA LOAD CURRENT ID
BNE B0!7FFF,+EXSI1 BNE WA, =CFP$M, EXS I 1 JUMP NO OVFL
ZER 00 ZER WA RESET FOR V/RAP
EXSIl ICV 00 EXSIl ICV WA BUMP ID VALUE
MOV AO 25 MOV WA^CURID STORE FOR NEXT
MOV EO'82 MOV WAJDVAL(XR) STORE ID VALUE
BRN ExixR BRN EXIXR EXIT WITH RESULT
Figure 1. Example of MINIMAL code (right) translated to
MICRAL (left) by MICTRAN.
16
EXIXR EQU $ EXIXR
HEX 329U
EXITS EQU $ EXITS
HEX 2A0tt
HEX 3237
HEX 0B03
EXNAM EQU $ EXNAM
EXNUL EQU $ EXNUL
EQU
$
HEX
329U
EQU
$
HEX
2A0tt
HEX
3237
HEX
0B03
EQU
$
HEX
3293
HEX
3290
HEX
030C
ADDR
EXITS
EQU
$
HEX
329B
ADDR
NULLS
HEX
n30C
ADDR
EXITS
EQU
$
HEX
320A25
HEX
09B07FFF
ADDR
EXSIl
HEX
UUOO
HEX
ICOO
HEX
32A025
HEX
32E082
HEX
03
ADDR
EXIXR
EXSID EQU $ EXSID
EXSIl HEX ICOO EXSIl
MOV 91+ STACK RESl'LT
LCW Ok LOAD NEXT CODE WORD
MOV 37 LOAD ENTRY ADDRESS
BRI 03 EXECUTE NEXT CODE
MOV 93 STACK NAME BASE
MOV 90 STACK NAME OFSET
BRN EXITS DO NEXT CODE WORD
MOV 9B, NULLS STACK NULL VALUE
BRN EXITS DO NEXT CODE WORD
MOV
0A,25
LOAD CURRENT ID
BNE
B0,7FFF
,+EXSIl
ZER
00
RESET FOP WRAP
ICV
00
BUMP ID VALUE
MOV
A0,25
STORE FOP NEXT T
MOV
EG, 82
STORE ID VALUE
BRN
EXIXR
EXIT WITH RESULT
ME
Figure 2. Example of translation from MICRAL to SPD
assembly code with no macro substitution.
17
EXIXR EQU $ EXIXR
HEX 6A *** MOV 9k STACK RESULT
EXITS EQU $ EXITS
HEX 2A0I+ LCW OU LOAD NEXT CODE WORD
HEX 89 *** MOV 37 LOAD ENTRY ADDRESS
HEX 0B03 BRI 03 EXECUTE NEXT CODE
EXNAM EQU $ EXNAM
HEX 68 *** MOV 93 STACK NAME BASE
HEX 60 *** MOV 90 STACK OFSET
HEX El *** BRN EXITS DO NEXT CODE WORD
EXNUL EQU $ EXNUL
HEX 68 *** MOV 9B, NULLS STACK NULL VALUE
ADDR NULLS
HEX El *** BRN EXITS DO NEXT CODE WORD
EXSID EQU $ EXSID
HEX 9A *** MOV 0A,25 LOAD CURRENT ID
HEX 25
HEX EC *** BNE BO, 7FFF^ +EXSI 1
HEX 7FFF
ADDR EXSIl
HEX ttUOO ZER 00 RESET FOR WRAP
EXSIl HEX ICOO EXSIl I CV 00 BI'MP ID VALUE
HEX 67 *** MOV A0,25 STORE FOP NEXT TIME
HEX 25
HEX 5D *** MOV E0,82 STORE ID VALUE
HEX EO *** BRN EXIXR EXIT WITH RESULT
Figure 3. Example of translation from MICRAL to SPD
assembly code with macro substitutions.
<***> indicates the use of a macro.
18
Bibliography
1) Dewar, R.B.K. and McCann, A. P., 'MACRO SPITBOL - a SNOBOLU Compiler',
Software - Practice and Experience, 7 (I977), pp. 95-113.
2) Dewar, R. B. K. and Goss, C. F. , MICRAL - Language Description and Documentation ,
available from the authors.
3) Priswold, R.E,, Poage, J.F. , and Polonsky, I. P., The SNOBOLli Programming
Language , Second Edition, Prentice-Hall, Englewood Cliffs, N.J.,
256 pp., 1971.
h) Dewar, R.B.K. , 'SPITBOL Version 2,0', IIT Internal Report, 78 pp., I97I.
5) Dewar, R.B.K., McCann, A. P., 'MINIMAL - A Machine Independent Assembly
Language', Computer Science Department Technical Report, Courant Institute
of Mathematical Sciences, No. 012.
6) SPD 20/20 Multi - station Intellegent Terminal System - System Description ,
Incoterm Corp., Wellesley Hilla, Mass., 02181, MS-7I65.I, January, I976.
7) PD/FMS Programmers ' Reference Manual , Incoterm Corp., Wellesley Hills,
Mass. , 02181, MS-7233.6.
8) Incoterm SPD Assembly Language , Incoterm Corp., Wellesley Hills, Mass.,
02181, MS-7215.2.
9) Morris, J.H. and Pratt, V. R, , 'A linear pattern matching algorithm'. Tech.
Report No. i+O, Computing Center, University of California, Berkley (I97O).
10) Aho, A. v., Hopcroft, J.E., and Ullman, J.D. , The Design and Analysis of
Computer Algorithms . Addison -Wesley , I976.
11) Gilmore, P.C. and Hoffman, A.J., 'A characterization of comparability
graphs and of interval graphs', Canadian Journal of Mathematics,
16 (196U), pp. 539-5it3.
19
12) Gavril, F. , 'Algorithms for minimum coloring, maximum clique, minimum
covering by cliques, and maximum independent set of a chordal graph'
SIAM Journal of Computing, 1 (I972), No. 2, pp. I8O-I87.
13) Golumbic, M.C. , Algorithmic Graph Theory and Perfect Graphs , Academic
Press. New York, N.Y., I96O .
Ill) Booth, K.S. and Leuker, G. S., 'Testing for the consecutive ones property,
interval graphs, and graph planarity using PQ-tree algorithms',
J. Computer Sys. Sci. , 13(1976), 335-379.
15) Gavril, F. , 'Algorithms for a maximum clique and a minimum independent
set of a circle graph', Networks, 3(1973), 261-273.
This book may be kept
FOURTEEN DAYS
A fine will be charged for each day the book is kept overtime.
1
CAYLORD 142
NYU
Comp.Sci.Dept .
TR-011
Dewar
MICRO SPITBOL.
C.2
NYU "
Com^pjSgj^Dept.
Dewar
C.2
AUTHOR
MICRO SPITBOL.
TITLE
DATE DUE
BORROWER'S NAME
N.Y.U. Courant Institute of
Mathematical Sciences
251 Mercer St.
New York, N. Y. 10012
